import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2025-07-06
 * Time: 15:27
 */


// LRU缓存
public class Test35 {
    static class ListNode {
        int value;
        int key;
        ListNode pre;
        ListNode next;

        ListNode(int key,int value) {
            this.value = value;
            this.key = key;
        }

        ListNode() {

        }
    }

    public class LRUCache {
        ListNode head = new ListNode();
        ListNode tail = new ListNode();
        int sum = 0, size = 0;
        Map<Integer,ListNode> hash = new HashMap<>();
        LRUCache(int capacity) {
            sum = capacity;
            head.next = tail;
            tail.pre = head;
        }

        public int get(int key) {
            if (hash.containsKey(key)) {
                toMove(hash.get(key));
                return hash.get(key).value;
            } else {
                return -1;
            }
        }

        private void toMove(ListNode t) {
            //1.先删除
            t.pre.next = t.next;
            t.next.pre = t.pre;
            //2.再移动到后面
            t.next = tail;
            tail.pre.next = t;
            t.pre = tail.pre;
            tail.pre = t;
        }

        public void put(int key,int value) {
            if(hash.containsKey(key)) {
                toMove(hash.get(key));
                hash.get(key).value = value;
                return;
            }
            // 先删除
            if(sum == size) {
                // 先哈希删
                hash.remove(head.next.key);
                head.next.next.pre = head;
                head.next = head.next.next;
                size--;
            }
            //添加
            ListNode t = new ListNode(key,value);
            hash.put(key,t);
            size++;
            t.next = tail;
            tail.pre.next = t;
            t.pre = tail.pre;
            tail.pre = t;
        }
    }

    public static void main(String[] args) {
        String[] operations = {"LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"};
        int[][] params = {{2}, {1, 1}, {2, 2}, {1}, {3, 3}, {2}, {4, 4}, {1}, {3}, {4}};

        Test35 test35 = new Test35();
        Test35.LRUCache lruCache = null;

        StringBuilder result = new StringBuilder("[");
        for (int i = 0; i < operations.length; i++) {
            switch (operations[i]) {
                case "LRUCache":
                    lruCache = test35.new LRUCache(params[i][0]);
                    result.append("null");
                    break;
                case "put":
                    lruCache.put(params[i][0], params[i][1]);
                    result.append("null");
                    break;
                case "get":
                    int val = lruCache.get(params[i][0]);
                    result.append(val);
                    break;
            }
            if (i != operations.length - 1) {
                result.append(", ");
            }
        }
        result.append("]");
        System.out.println(result);
    }
}
